'''
钢条切割问题--动态规划解法
    递归算法由于重复求解相同子问题,效率极低
    动态规划的思想:
        每个子问题只求解一次,保存求解结果
        之后需要此问题时,只需查找保存的结果
'''


def cut_rod_dp(p, n):
    """
    动态规划求解钢条切割问题（修正版）

    问题描述：
        给定一段长度为n的钢条和一个价格数组p，其中p[i]表示长度为i的钢条的售价。
        可以将钢条切割成任意段，求切割后能获得的最大总收益。

    参数:
        p: 价格数组，p[i]表示长度为i的钢条的价格（索引从1开始有效）
        n: 需要切割的钢条总长度

    返回:
        长度为n的钢条的最大收益
    """
    # 创建一个数组r用于存储子问题的解，r[i]表示长度为i的钢条的最大收益
    # 初始化r[0] = 0，长度为0的钢条收益为0
    r = [0] * (n + 1)

    # 计算长度从1到n的钢条的最大收益
    for i in range(1, n + 1):
        # 初始化当前长度i的最大收益为0
        max_profit = 0

        # 尝试所有可能的切割位置j（从1到i）
        # j表示第一段的长度，剩下的长度为i-j
        for j in range(1, i + 1):
            # 计算当前切割方案的收益：长度j的价格 + 剩余长度(i-j)的最大收益
            current_profit = p[j] + r[i - j]

            # 更新最大收益
            if current_profit > max_profit:
                max_profit = current_profit

        # 存储长度i的最大收益
        r[i] = max_profit

    # 返回长度为n的钢条的最大收益
    return r[n]


# 示例用法
if __name__ == "__main__":
    # 价格表：p[0]未使用，p[1]是长度1的价格，p[2]是长度2的价格，以此类推
    price = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]

    # 计算长度为4的钢条的最大收益
    rod_length = 4
    max_profit = cut_rod_dp(price, rod_length)
    print(f"长度为{rod_length}的钢条的最大收益为：{max_profit}")  # 应输出10